package org.lanqiao.practice_2;

import org.junit.Test;

public class TestDriver6 {
	//快速排序

	@Test
	public void Test_quickSort() {
		// 创建一个数组
		int[] arraySort = new int[] { 55, 84, 15, 47, 26, 48, 23, 15 };
		System.out.println("排序前：");
		// 输出排序前的数组元素
		outputArray(arraySort);
		System.out.println();
		System.out.println("排序后：");
		quickSort(arraySort, 0, arraySort.length - 1);
		outputArray(arraySort);

	}

	public void quickSort(int[] ar, int low, int high) {
		if (low < high) {
			// 对数组进行分区
			int index = partitionSelf(ar, low, high);
			// 再次对分区的数组进行左分区递归
			quickSort(ar, low, index - 1);
			// 对数组进行右分区的递归
			quickSort(ar, index + 1, high);
		}
	}

	private int partition(int[] ar, int low, int high) {
		// 指定一个参考量
		int temp = ar[low];
		while (low < high) {
			// 依次从右向左寻找，当发现high的数比temp小时，调换此数
			while (low < high && ar[high] >= temp) {
				high--;
			}
			ar[low] = ar[high];
			// 依次从左向右寻找，当发现有比temp的数时把次数调换到high指针处
			while (low < high && ar[low] <= temp) {
				low++;
			}
			ar[high] = ar[low];
		}
		// 把作为参考量的数放到low指针和high指针相遇的地方
		ar[low] = temp;
		return low;
	}

	public void outputArray(int[] ar) {
		for (int i : ar) {
			System.out.print(i + "\t");
		}
	}

	private int partitionSelf(int[] ar, int low, int high) {
		// 把第一个数存起来
		int temp = ar[low];
		while (low < high) {
			// 从右向左寻找比temp小的数
			while (low < high && temp <= ar[high]) {
				high--;
			}
			ar[low] = ar[high];
			// 从右向左寻找
			while (low < high && temp >= ar[low]) {
				low++;
			}
			ar[high] = ar[low];
		}
		ar[low] = temp;
		return low;
	}

}
